package com.fengye.algorithms.alibaba;

/**
 * 长度为 n 的数组，其中只有 2 个数字出现了奇数次，其他均出现偶数次，问如何使
 * 用优秀的时空复杂度快速找到这个数字
 *
 * 思路：主要是利用异或定理，若 a^b=x，则 a=b^x，b=x^a。
 * @Author fengye
 * @Date 2023/4/12 17:56
 **/
public class TwoOddNum27 {
    public static void main(String[] args) {
        int[] nums = {2,3,4,5,2,5};
        int[] r = new TwoOddNum27().twoOdd(nums);
        System.out.println(r[0] + " " + r[1]);
    }
    public int[] twoOdd(int[] nums) {
        int x = nums[0];
        // 先取得到所有异或值，最后相当于a^b
        for(int i=1;i<nums.length;i++) {
            x ^= nums[i];
        }

        String xBinary = Integer.toBinaryString(x);
        int t = -1;
        // 因为 x 中第 k 位为 1 表示 a 或 b 中有一个数的第 k 位也为 1，另一个数第 k 位为
        // 0；假设 a 的第 k 位为 1；
        for(int i=xBinary.length()-1;i>=0;i--) {
            if('1' == xBinary.charAt(i)) {
                t = xBinary.length()-1 - i;
                break;
            }
        }
        int b = x;
        // 将 x 与数组中第 k 位为 1 的所有数字进行异或，最终结果得到 b；
        for (int i=0;i<nums.length; i++) {
            String iBinary = Integer.toBinaryString(nums[i]);
            if(iBinary.length() > t && iBinary.charAt(iBinary.length() -1 - t) == '1') {
                b ^= nums[i];
            }
        }
        // 最后a = b ^ x
        int a = b ^ x;

        return new int[]{a,b};
    }
}
